package com.example.leetcode.trainingcamp.week5.Thursday;

/**
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4
 * 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次
 * 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 *
 * <p>给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test153 {

    public int findMin(int[] nums) {
        int high = nums.length - 1;
        int low = 0;
        if (high ==0){
            return nums[0];
        }
        while (low <= high){
            int mid = low + (high - low) / 2;
            if (mid == 0 && nums[0] < nums[nums.length-1]) return nums[0];
            if (mid != 0 && nums[mid] < nums[mid -1]) return nums[mid];
            if (mid == nums.length -1 && nums[mid] < nums[0]) return nums[nums.length-1];
            if (nums[nums.length -1] < nums[0]){
                if (nums[mid] < nums[nums.length -1]){
                    high = mid -1;
                }else {
                    low = mid +1;
                }
            }else {
                if (nums[0] < nums[mid]){
                    high = mid -1;
                }else {
                    low = mid +1;
                }
            }
        }
        return -1;
    }
}


class Demo153{
  public static void main(String[] args) {
      int[] nums = {11,13,15,17};
      Test153 t1 = new Test153();
    System.out.println(t1.findMin(nums));
  }
}